package acwing;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class quickSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++ ) {
            arr[i] = in.nextInt();
        }
        quick_Sort(arr, 0, n - 1);
        for(int i = 0; i < n; i ++ ){
            System.out.print(arr[i] + " ");
        }
    }

    public static void quick_Sort(int[] arr, int left, int right){
        if(left >= right) return; //当左右哨兵相遇时结束
        int x = arr[(left + right) / 2], i = left - 1, j = right + 1; //令x为分界点
        //使得x前的数都小于x,在x后的数都大于x
        while(i < j){//在两哨兵未相遇时
            do {i ++ ;}while (arr[i] < x);//找比分界点大的
            do {j -- ;}while (arr[j] > x);//找比分界点小的
            if(i < j){//找到之后确保哨兵未相遇并将找出的数交换位置
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        quick_Sort(arr, left, j);//递归排序前半部分
        quick_Sort(arr, j + 1 , right);//递归排序后半部分
    }
}
